package org.example.myleet.p1310;

/**
 * 2 ms
 * 差分数组法，注意如果循环里面去判断索引是否小于0是比较浪费时间的，通过将数组扩充到相应的位置以除去if判断可以加速
 * 类比加法的差分数组法，由于xor也符合交换律，因此也可以使用差分数组法
 * 求q[left, right] = arr[left]^...^arr[right]，即要求diff[left-1] ^ diff[right]
 * 推导，diff[left-1] = arr[0]^arr[1]^...^arr[left-1]，diff[right] = arr[0]^arr[1]^...^arr[left-1]^arr[left]^...^arr[right]
 * diff[left-1] ^ diff[right] = (arr[0]^arr[1]^...^arr[left-1]) ^ (arr[0]^arr[1]^...^arr[left-1]^arr[left]^...^arr[right])
 * = (arr[0]^arr[1]^...^arr[left-1]) ^ (arr[0]^arr[1]^...^arr[left-1]) ^ (arr[left]^...^arr[right]) = arr[left]^...^arr[right]
 */
public class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        //每个位置存储了从0...i的arr中元素的xor值
        int[] diff = new int[arr.length + 1];
        //0位置预留给索引小于0的情况，都为0
        diff[0] = 0;
        diff[1] = arr[0];
        for (int i = 1; i < arr.length; ++i) {
            diff[i+1] = diff[i] ^ arr[i];
        }
        int[] reply = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            reply[i] = diff[queries[i][0]] ^ diff[queries[i][1] + 1];
        }
        return reply;
    }
}
